What is the time complexity of the following code snippet?int count = ...
The outer loop runs log2(n) times, the middle loop runs i times, and the inner loop runs log2(n) times. Hence, the time complexity is O(n^2).
What is the time complexity of the following code snippet?int count = ...
Understanding the Code Snippet
The given code snippet consists of three nested loops, which we will analyze to determine its time complexity.
Outer Loop Analysis
- The outer loop runs with `i` starting from 1 and doubling each iteration until `i` exceeds `n`.
- The iterations for `i` will be: 1, 2, 4, 8, ..., up to the largest power of 2 less than or equal to `n`.
- This results in approximately `log2(n)` iterations.
Middle Loop Analysis
- The middle loop iterates from `j = 1` to `i`.
- The number of iterations depends on the current value of `i`, which varies from 1 to `n`.
- In the worst case, when `i` is at its maximum value (i.e., `n`), the middle loop runs `n` times.
Inner Loop Analysis
- The inner loop runs with `k`, starting from 1 and doubling each iteration until it exceeds `n`.
- Similar to the outer loop, this loop also runs for approximately `log2(n)` iterations.
Combining the Complexity
- The total count of operations can be calculated as follows:
- For each value of `i`, we have:
- Middle loop executes `i` times.
- Inner loop executes `log2(n)` times.
- The total operations can be expressed as:
\[
Total = \sum_{i=1}^{n} (i \cdot log2(n))
\]
- The sum of `i` from 1 to `n` is \(\frac{n(n+1)}{2}\), which simplifies to \(O(n^2)\).
Final Complexity
- Thus, the overall time complexity of the entire code snippet is:
\[
O(n^2 \cdot log2(n)) = O(n^2)
\]
- Therefore, the correct answer is option **'D'**: O(n²).
To make sure you are not studying endlessly, EduRev has designed Software Development study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Software Development.